package solution.tree;

import java.util.HashSet;
import java.util.Set;

import lib.tree.BNode;
import lib.tree.TreeUtil;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 * 
 *         http://www.sureinterview.com/shwqst/114001
 */
public class LowestCommonAncestor {

	BNode a;

	BNode b;

	BNode lca;

	int numFoundNode;

	BNode getInBST(BNode root, Integer value) {
		BNode curNode = root;
		while (curNode != null) {
			if (curNode.value.equals(value))
				return curNode;

			if (value < curNode.value) {
				curNode = curNode.left;
				continue;
			}

			curNode = curNode.right;
		}
		return null;
	}

	/**
	 * Find the lowest common ancestor of node a and b in BST. no parent node to
	 * trace back.
	 * 
	 * Assume: left < root <= right
	 * 
	 * @param root
	 * @param a
	 * @param b
	 * @return the lowest common ancestor of a and b.
	 */
	public BNode getLCA(BNode root, BNode a, BNode b) {
		if (root == null || a == null || b == null)
			return null; // input is not valid

		BNode lca = null;

		// let la <= lb.
		Integer ia = (a.value < b.value ? a.value : b.value);
		Integer ib = (a.value + b.value - ia);

		BNode curNode = root;
		while (curNode != null) {
			/*
			 * val is the value of current node.
			 */

			// case 1. val < a <= b. Because val is on the root, the lowest
			// common ancestor must be on the right branch.
			if (curNode.value < ia) {
				curNode = curNode.right;
				continue;
			}

			// case 2. val == a <= b
			if (curNode.value.equals(ia)) {
				do {
					lca = curNode;
					if (lca == a) {
						break;
					}
					curNode = curNode.right;
					if (curNode == null || !curNode.value.equals(ia))
						return null; // the node a does not exist.
				} while (true);

				// double check if note b is really in the tree
				if (getInBST(lca, ib) == null) {
					lca = null;
				}
				return lca;
			}

			// case 3. a < val < b
			if (curNode.value < ib) {
				lca = curNode;
				if (getInBST(lca, ia) == null || getInBST(lca, ib) == null) {
					lca = null;
				}
				return lca;
			}

			// case 4. a < val == b
			if (curNode.value == ib) {
				lca = curNode;
				if (getInBST(lca, ia) == null) {
					lca = null;
				}
				return lca;
			}
			// case 5. a <= b < val
			curNode = curNode.left;
		}
		return null;
	}

	/**
	 * check http://www.sureinterview.com/shwqst/114001 Given the parent of each
	 * node, find the lowest common ancestor of node a and b.
	 * 
	 * @param root
	 *            root of the tree
	 * @param a
	 * @param b
	 * @return the parent node of a and b
	 */
	public BNode getLCA2(BNode root, BNode a, BNode b) {
		// 1. trace one node to the root
		Set<BNode> set = new HashSet<BNode>();
		BNode t = a;
		while (t != null) {
			set.add(t);
			t = t.parent;
		}

		// 2. trace another node towards to root. The common ancestors are those
		// nodes also in the set from step 1.
		t = b;
		while (t != null) {
			if (set.contains(t))
				return t;
			t = t.parent;
		}
		return null; // not found
	}

	BNode getLCA3(BNode root, BNode a, BNode b) {
		lca = null;
		this.a = a;
		this.b = b;
		numFoundNode = 0;
		getLCA3_rec(root);
		return lca;
	}

	int getLCA3_rec(BNode root) {
		int num = 0;
		if (root == null || numFoundNode >= 2)
			return 0;

		if (root == a || root == b) {
			num++;
			numFoundNode++;
		}

		num += getLCA3_rec(root.left);
		num += getLCA3_rec(root.right);
		if (num == 2 && lca == null) {
			lca = root;
		}
		return num;
	}

	@Test
	public void test() {
		BNode tree = new TreeUtil()
				.makeTree("15(12(8(1,10),14(13,)),23(17,25(24,)))");

		Integer data[][] = {
				//
				{ 1, 12, 12 },//
				{ 8, 25, 15 },//
				{ 8, 13, 12 },//
				{ 17, 24, 23 },//
				{ 23, 24, 23 } };

		for (Integer[] element : data) {
			BNode a = getInBST(tree, element[0]), //
			b = getInBST(tree, element[1]), //
			c = getInBST(tree, element[2]);
			Assert.assertEquals(c, getLCA(tree, a, b));
			Assert.assertEquals(c, getLCA2(tree, a, b));
			Assert.assertEquals(c, getLCA3(tree, a, b));
		}

	}
}
